MAX_INT = 101


class Solution:
    def strangePrinter(self, s: str) -> int:
        size = len(s)

        s = [ord(ch) - 97 for ch in s]

        # dp[i][j][k] = [i,j]最早打印k的最小次数 (k=26时，是dp[i][j]的最小值）
        dp = [[[MAX_INT] * 26 for _ in range(size)] for _ in range(size)]

        # 处理长度为1的字符串
        for i in range(size):
            for k in range(26):
                dp[i][i][k] = 2
            dp[i][i][s[i]] = 1

        # 处理长度为2的字符串
        for i in range(size - 1):
            if s[i] == s[i + 1]:
                for k in range(26):
                    dp[i][i + 1][k] = 2
                dp[i][i + 1][s[i]] = 1
            else:
                for k in range(26):
                    dp[i][i + 1][k] = 3
                dp[i][i + 1][s[i]] = dp[i][i + 1][s[i + 1]] = 2

        # 处理长度大于等于3的字符串
        for length in range(2, size):
            for i in range(size - length):
                j = i + length
                for k in range(26):
                    if k == s[i]:
                        dp[i][j][k] = dp[i + 1][j][k]
                    elif k == s[j]:
                        dp[i][j][k] = dp[i][j - 1][k]
                    else:
                        dp[i][j][k] = min(dp[i + 1][j][k] + (0 if s[i] == s[i + 1] else 1),
                                          dp[i][j - 1][k] + (0 if s[j] == s[j - 1] else 1))
                max_val = min(dp[i][j]) + 1
                for k in range(26):
                    dp[i][j][k] = min(dp[i][j][k], max_val)

        # for row in dp:
        #     print(row)

        return min(dp[0][-1])


if __name__ == "__main__":
    print(Solution().strangePrinter("aaabbb"))  # 2
    print(Solution().strangePrinter("aba"))  # 2

    # 测试用例40/200
    print(Solution().strangePrinter("abcabc"))  # 5

    # 测试用例55/200
    print(Solution().strangePrinter("tbgtgb"))  # 4
